package leetcode_top;

import java.util.*;

import org.junit.*;

public class Ex131 {
    class Solution1 {
        public List<List<String>> partition(String s) {
            dfs(s.toCharArray(), 0, 0, new ArrayList<>());
            return res;
        }

        List<List<String>> res = new ArrayList<>();

        public void dfs(char[] cs, int start, int idx, List<String> cur) {
            if (idx == cs.length) {
                int count = 0;
                for (int i = 0; i < cur.size(); i++) {
                    count += cur.get(i).length();
                }
                if (count == cs.length)
                    res.add(new ArrayList<>(cur));
                return;
            }
            dfs(cs, start, idx + 1, cur);
            if (test(cs, start, idx)) {
                cur.add(new String(cs, start, idx - start + 1));
                dfs(cs, idx + 1, idx + 1, cur);
                cur.remove(cur.size() - 1);
            }
        }

        public boolean test(char[] cs, int lo, int hi) {
            if (lo == hi)
                return true;
            for (int i = lo; i <= (hi + lo) / 2; i++) {
                if (cs[lo] != cs[hi])
                    return false;
            }
            return true;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.partition("aab"));
    }

    @Test
    public void tes1t() {
        // Solution s = new Solution();
        // System.out.println(s.test("aabaabba".toCharArray(), 1,2));
    }

    class Solution {
        public List<List<String>> partition(String s) {
            int len = s.length();
            // int[][] f = new int[len][len];
            boolean[][] f = new boolean[len][len];
            for (int i = 0; i < len; i++) {
                f[i][i] = true;
            }
            char[] cs = s.toCharArray();
            for (int j = 0; j < len; j++) {
                for (int i = j; i >= 0; i--) {
                    if (i == j)
                        f[i][j] = true;
                    else if (i + 1 == j)
                        f[i][j] = cs[i] == cs[j];
                    else
                        f[i][j] = f[i + 1][j - 1] && cs[i] == cs[j];
                }
            }
            dfs(f, 0, new ArrayList<>(), s);
            return res;
        }

        List<List<String>> res = new ArrayList<>();

        public void dfs(boolean[][] f, int idx, List<String> cur, String s) {
            if (idx == f.length) {
                res.add(new ArrayList<>(cur));
                return;
            }
            for (int i = idx; i < f.length; i++) {
                if (f[idx][i]) {
                    cur.add(s.substring(idx, i + 1));
                    dfs(f, i + 1, cur, s);
                    cur.remove(cur.size() - 1);
                }
            }

        }

    }

    /*
     * 
     * 
     * [["a","a","b","a","a","b","b","a","b","b","b","a","b","b"],["a","a","b","a",
     * "a","b","b","a","b","b","b","a","bb"],["a","a","b","a","a","b","b","a","b",
     * "b","bab","b"],["a","a","b","a","a","b","b","a","b","bb","a","b","b"],["a",
     * "a","b","a","a","b","b","a","b","bb","a","bb"],["a","a","b","a","a","b","b",
     * "a","b","bbabb"],["a","a","b","a","a","b","b","a","bb","b","a","b","b"],["a",
     * "a","b","a","a","b","b","a","bb","b","a","bb"],["a","a","b","a","a","b","b",
     * "a","bb","bab","b"],["a","a","b","a","a","b","b","a","bbb","a","b","b"],["a",
     * "a","b","a","a","b","b","a","bbb","a","bb"],["a","a","b","a","a","b","b",
     * "abbba","b","b"],["a","a","b","a","a","b","b","abbba","bb"],["a","a","b","a",
     * "a","b","bab","b","b","a","b","b"],["a","a","b","a","a","b","bab","b","b","a"
     * ,"bb"],["a","a","b","a","a","b","bab","b","bab","b"],["a","a","b","a","a","b"
     * ,"bab","bb","a","b","b"],["a","a","b","a","a","b","bab","bb","a","bb"],["a",
     * "a","b","a","a","b","bab","bbabb"],["a","a","b","a","a","b","babbbab","b"],[
     * "a","a","b","a","a","bb","a","b","b","b","a","b","b"],["a","a","b","a","a",
     * "bb","a","b","b","b","a","bb"],["a","a","b","a","a","bb","a","b","b","bab",
     * "b"],["a","a","b","a","a","bb","a","b","bb","a","b","b"],["a","a","b","a","a"
     * ,"bb","a","b","bb","a","bb"],["a","a","b","a","a","bb","a","b","bbabb"],["a",
     * "a","b","a","a","bb","a","bb","b","a","b","b"],["a","a","b","a","a","bb","a",
     * "bb","b","a","bb"],["a","a","b","a","a","bb","a","bb","bab","b"],["a","a","b"
     * ,"a","a","bb","a","bbb","a","b","b"],["a","a","b","a","a","bb","a","bbb","a",
     * "bb"],["a","a","b","a","a","bb","abbba","b","b"],["a","a","b","a","a","bb",
     * "abbba","bb"],["a","a","b","a","a","bbabb","b","a","b","b"],["a","a","b","a",
     * "a","bbabb","b","a","bb"],["a","a","b","a","a","bbabb","bab","b"],["a","a",
     * "b","a","a","bbabbbabb"],["a","a","b","a","abba","b","b","b","a","b","b"],[
     * "a","a","b","a","abba","b","b","b","a","bb"],["a","a","b","a","abba","b","b",
     * "bab","b"],["a","a","b","a","abba","b","bb","a","b","b"],["a","a","b","a",
     * "abba","b","bb","a","bb"],["a","a","b","a","abba","b","bbabb"],["a","a","b",
     * "a","abba","bb","b","a","b","b"],["a","a","b","a","abba","bb","b","a","bb"],[
     * "a","a","b","a","abba","bb","bab","b"],["a","a","b","a","abba","bbb","a","b",
     * "b"],["a","a","b","a","abba","bbb","a","bb"],["a","a","b","aa","b","b","a",
     * "b","b","b","a","b","b"],["a","a","b","aa","b","b","a","b","b","b","a","bb"],
     * ["a","a","b","aa","b","b","a","b","b","bab","b"],["a","a","b","aa","b","b",
     * "a","b","bb","a","b","b"],["a","a","b","aa","b","b","a","b","bb","a","bb"],[
     * "a","a","b","aa","b","b","a","b","bbabb"],["a","a","b","aa","b","b","a","bb",
     * "b","a","b","b"],["a","a","b","aa","b","b","a","bb","b","a","bb"],["a","a",
     * "b","aa","b","b","a","bb","bab","b"],["a","a","b","aa","b","b","a","bbb","a",
     * "b","b"],["a","a","b","aa","b","b","a","bbb","a","bb"],["a","a","b","aa","b",
     * "b","abbba","b","b"],["a","a","b","aa","b","b","abbba","bb"],["a","a","b",
     * "aa","b","bab","b","b","a","b","b"],["a","a","b","aa","b","bab","b","b","a",
     * "bb"],["a","a","b","aa","b","bab","b","bab","b"],["a","a","b","aa","b","bab",
     * "bb","a","b","b"],["a","a","b","aa","b","bab","bb","a","bb"],["a","a","b",
     * "aa","b","bab","bbabb"],["a","a","b","aa","b","babbbab","b"],["a","a","b",
     * "aa","bb","a","b","b","b","a","b","b"],["a","a","b","aa","bb","a","b","b","b"
     * ,"a","bb"],["a","a","b","aa","bb","a","b","b","bab","b"],["a","a","b","aa",
     * "bb","a","b","bb","a","b","b"],["a","a","b","aa","bb","a","b","bb","a","bb"],
     * ["a","a","b","aa","bb","a","b","bbabb"],["a","a","b","aa","bb","a","bb","b",
     * "a","b","b"],["a","a","b","aa","bb","a","bb","b","a","bb"],["a","a","b","aa",
     * "bb","a","bb","bab","b"],["a","a","b","aa","bb","a","bbb","a","b","b"],["a",
     * "a","b","aa","bb","a","bbb","a","bb"],["a","a","b","aa","bb","abbba","b","b"]
     * ,["a","a","b","aa","bb","abbba","bb"],["a","a","b","aa","bbabb","b","a","b",
     * "b"],["a","a","b","aa","bbabb","b","a","bb"],["a","a","b","aa","bbabb","bab",
     * "b"],["a","a","b","aa","bbabbbabb"],["a","a","baab","b","a","b","b","b","a",
     * "b","b"],["a","a","baab","b","a","b","b","b","a","bb"],["a","a","baab","b",
     * "a","b","b","bab","b"],["a","a","baab","b","a","b","bb","a","b","b"],["a","a"
     * ,"baab","b","a","b","bb","a","bb"],["a","a","baab","b","a","b","bbabb"],["a",
     * "a","baab","b","a","bb","b","a","b","b"],["a","a","baab","b","a","bb","b","a"
     * ,"bb"],["a","a","baab","b","a","bb","bab","b"],["a","a","baab","b","a","bbb",
     * "a","b","b"],["a","a","baab","b","a","bbb","a","bb"],["a","a","baab","b",
     * "abbba","b","b"],["a","a","baab","b","abbba","bb"],["a","a","baab","bab","b",
     * "b","a","b","b"],["a","a","baab","bab","b","b","a","bb"],["a","a","baab",
     * "bab","b","bab","b"],["a","a","baab","bab","bb","a","b","b"],["a","a","baab",
     * "bab","bb","a","bb"],["a","a","baab","bab","bbabb"],["a","a","baab","babbbab"
     * ,"b"],["a","aba","a","b","b","a","b","b","b","a","b","b"],["a","aba","a","b",
     * "b","a","b","b","b","a","bb"],["a","aba","a","b","b","a","b","b","bab","b"],[
     * "a","aba","a","b","b","a","b","bb","a","b","b"],["a","aba","a","b","b","a",
     * "b","bb","a","bb"],["a","aba","a","b","b","a","b","bbabb"],["a","aba","a","b"
     * ,"b","a","bb","b","a","b","b"],["a","aba","a","b","b","a","bb","b","a","bb"],
     * ["a","aba","a","b","b","a","bb","bab","b"],["a","aba","a","b","b","a","bbb",
     * "a","b","b"],["a","aba","a","b","b","a","bbb","a","bb"],["a","aba","a","b",
     * "b","abbba","b","b"],["a","aba","a","b","b","abbba","bb"],["a","aba","a","b",
     * "bab","b","b","a","b","b"],["a","aba","a","b","bab","b","b","a","bb"],["a",
     * "aba","a","b","bab","b","bab","b"],["a","aba","a","b","bab","bb","a","b","b"]
     * ,["a","aba","a","b","bab","bb","a","bb"],["a","aba","a","b","bab","bbabb"],[
     * "a","aba","a","b","babbbab","b"],["a","aba","a","bb","a","b","b","b","a","b",
     * "b"],["a","aba","a","bb","a","b","b","b","a","bb"],["a","aba","a","bb","a",
     * "b","b","bab","b"],["a","aba","a","bb","a","b","bb","a","b","b"],["a","aba",
     * "a","bb","a","b","bb","a","bb"],["a","aba","a","bb","a","b","bbabb"],["a",
     * "aba","a","bb","a","bb","b","a","b","b"],["a","aba","a","bb","a","bb","b","a"
     * ,"bb"],["a","aba","a","bb","a","bb","bab","b"],["a","aba","a","bb","a","bbb",
     * "a","b","b"],["a","aba","a","bb","a","bbb","a","bb"],["a","aba","a","bb",
     * "abbba","b","b"],["a","aba","a","bb","abbba","bb"],["a","aba","a","bbabb","b"
     * ,"a","b","b"],["a","aba","a","bbabb","b","a","bb"],["a","aba","a","bbabb",
     * "bab","b"],["a","aba","a","bbabbbabb"],["a","aba","abba","b","b","b","a","b",
     * "b"],["a","aba","abba","b","b","b","a","bb"],["a","aba","abba","b","b","bab",
     * "b"],["a","aba","abba","b","bb","a","b","b"],["a","aba","abba","b","bb","a",
     * "bb"],["a","aba","abba","b","bbabb"],["a","aba","abba","bb","b","a","b","b"],
     * ["a","aba","abba","bb","b","a","bb"],["a","aba","abba","bb","bab","b"],["a",
     * "aba","abba","bbb","a","b","b"],["a","aba","abba","bbb","a","bb"],["aa","b",
     * "a","a","b","b","a","b","b","b","a","b","b"],["aa","b","a","a","b","b","a",
     * "b","b","b","a","bb"],["aa","b","a","a","b","b","a","b","b","bab","b"],["aa",
     * "b","a","a","b","b","a","b","bb","a","b","b"],["aa","b","a","a","b","b","a",
     * "b","bb","a","bb"],["aa","b","a","a","b","b","a","b","bbabb"],["aa","b","a",
     * "a","b","b","a","bb","b","a","b","b"],["aa","b","a","a","b","b","a","bb","b",
     * "a","bb"],["aa","b","a","a","b","b","a","bb","bab","b"],["aa","b","a","a","b"
     * ,"b","a","bbb","a","b","b"],["aa","b","a","a","b","b","a","bbb","a","bb"],[
     * "aa","b","a","a","b","b","abbba","b","b"],["aa","b","a","a","b","b","abbba",
     * "bb"],["aa","b","a","a","b","bab","b","b","a","b","b"],["aa","b","a","a","b",
     * "bab","b","b","a","bb"],["aa","b","a","a","b","bab","b","bab","b"],["aa","b",
     * "a","a","b","bab","bb","a","b","b"],["aa","b","a","a","b","bab","bb","a","bb"
     * ],["aa","b","a","a","b","bab","bbabb"],["aa","b","a","a","b","babbbab","b"],[
     * "aa","b","a","a","bb","a","b","b","b","a","b","b"],["aa","b","a","a","bb","a"
     * ,"b","b","b","a","bb"],["aa","b","a","a","bb","a","b","b","bab","b"],["aa",
     * "b","a","a","bb","a","b","bb","a","b","b"],["aa","b","a","a","bb","a","b",
     * "bb","a","bb"],["aa","b","a","a","bb","a","b","bbabb"],["aa","b","a","a","bb"
     * ,"a","bb","b","a","b","b"],["aa","b","a","a","bb","a","bb","b","a","bb"],[
     * "aa","b","a","a","bb","a","bb","bab","b"],["aa","b","a","a","bb","a","bbb",
     * "a","b","b"],["aa","b","a","a","bb","a","bbb","a","bb"],["aa","b","a","a",
     * "bb","abbba","b","b"],["aa","b","a","a","bb","abbba","bb"],["aa","b","a","a",
     * "bbabb","b","a","b","b"],["aa","b","a","a","bbabb","b","a","bb"],["aa","b",
     * "a","a","bbabb","bab","b"],["aa","b","a","a","bbabbbabb"],["aa","b","a",
     * "abba","b","b","b","a","b","b"],["aa","b","a","abba","b","b","b","a","bb"],[
     * "aa","b","a","abba","b","b","bab","b"],["aa","b","a","abba","b","bb","a","b",
     * "b"],["aa","b","a","abba","b","bb","a","bb"],["aa","b","a","abba","b","bbabb"
     * ],["aa","b","a","abba","bb","b","a","b","b"],["aa","b","a","abba","bb","b",
     * "a","bb"],["aa","b","a","abba","bb","bab","b"],["aa","b","a","abba","bbb","a"
     * ,"b","b"],["aa","b","a","abba","bbb","a","bb"],["aa","b","aa","b","b","a","b"
     * ,"b","b","a","b","b"],["aa","b","aa","b","b","a","b","b","b","a","bb"],["aa",
     * "b","aa","b","b","a","b","b","bab","b"],["aa","b","aa","b","b","a","b","bb",
     * "a","b","b"],["aa","b","aa","b","b","a","b","bb","a","bb"],["aa","b","aa","b"
     * ,"b","a","b","bbabb"],["aa","b","aa","b","b","a","bb","b","a","b","b"],["aa",
     * "b","aa","b","b","a","bb","b","a","bb"],["aa","b","aa","b","b","a","bb","bab"
     * ,"b"],["aa","b","aa","b","b","a","bbb","a","b","b"],["aa","b","aa","b","b",
     * "a","bbb","a","bb"],["aa","b","aa","b","b","abbba","b","b"],["aa","b","aa",
     * "b","b","abbba","bb"],["aa","b","aa","b","bab","b","b","a","b","b"],["aa","b"
     * ,"aa","b","bab","b","b","a","bb"],["aa","b","aa","b","bab","b","bab","b"],[
     * "aa","b","aa","b","bab","bb","a","b","b"],["aa","b","aa","b","bab","bb","a",
     * "bb"],["aa","b","aa","b","bab","bbabb"],["aa","b","aa","b","babbbab","b"],[
     * "aa","b","aa","bb","a","b","b","b","a","b","b"],["aa","b","aa","bb","a","b",
     * "b","b","a","bb"],["aa","b","aa","bb","a","b","b","bab","b"],["aa","b","aa",
     * "bb","a","b","bb","a","b","b"],["aa","b","aa","bb","a","b","bb","a","bb"],[
     * "aa","b","aa","bb","a","b","bbabb"],["aa","b","aa","bb","a","bb","b","a","b",
     * "b"],["aa","b","aa","bb","a","bb","b","a","bb"],["aa","b","aa","bb","a","bb",
     * "bab","b"],["aa","b","aa","bb","a","bbb","a","b","b"],["aa","b","aa","bb","a"
     * ,"bbb","a","bb"],["aa","b","aa","bb","abbba","b","b"],["aa","b","aa","bb",
     * "abbba","bb"],["aa","b","aa","bbabb","b","a","b","b"],["aa","b","aa","bbabb",
     * "b","a","bb"],["aa","b","aa","bbabb","bab","b"],["aa","b","aa","bbabbbabb"],[
     * "aa","baab","b","a","b","b","b","a","b","b"],["aa","baab","b","a","b","b","b"
     * ,"a","bb"],["aa","baab","b","a","b","b","bab","b"],["aa","baab","b","a","b",
     * "bb","a","b","b"],["aa","baab","b","a","b","bb","a","bb"],["aa","baab","b",
     * "a","b","bbabb"],["aa","baab","b","a","bb","b","a","b","b"],["aa","baab","b",
     * "a","bb","b","a","bb"],["aa","baab","b","a","bb","bab","b"],["aa","baab","b",
     * "a","bbb","a","b","b"],["aa","baab","b","a","bbb","a","bb"],["aa","baab","b",
     * "abbba","b","b"],["aa","baab","b","abbba","bb"],["aa","baab","bab","b","b",
     * "a","b","b"],["aa","baab","bab","b","b","a","bb"],["aa","baab","bab","b",
     * "bab","b"],["aa","baab","bab","bb","a","b","b"],["aa","baab","bab","bb","a",
     * "bb"],["aa","baab","bab","bbabb"],["aa","baab","babbbab","b"],["aabaa","b",
     * "b","a","b","b","b","a","b","b"],["aabaa","b","b","a","b","b","b","a","bb"],[
     * "aabaa","b","b","a","b","b","bab","b"],["aabaa","b","b","a","b","bb","a","b",
     * "b"],["aabaa","b","b","a","b","bb","a","bb"],["aabaa","b","b","a","b","bbabb"
     * ],["aabaa","b","b","a","bb","b","a","b","b"],["aabaa","b","b","a","bb","b",
     * "a","bb"],["aabaa","b","b","a","bb","bab","b"],["aabaa","b","b","a","bbb","a"
     * ,"b","b"],["aabaa","b","b","a","bbb","a","bb"],["aabaa","b","b","abbba","b",
     * "b"],["aabaa","b","b","abbba","bb"],["aabaa","b","bab","b","b","a","b","b"],[
     * "aabaa","b","bab","b","b","a","bb"],["aabaa","b","bab","b","bab","b"],[
     * "aabaa","b","bab","bb","a","b","b"],["aabaa","b","bab","bb","a","bb"],[
     * "aabaa","b","bab","bbabb"],["aabaa","b","babbbab","b"],["aabaa","bb","a","b",
     * "b","b","a","b","b"],["aabaa","bb","a","b","b","b","a","bb"],["aabaa","bb",
     * "a","b","b","bab","b"],["aabaa","bb","a","b","bb","a","b","b"],["aabaa","bb",
     * "a","b","bb","a","bb"],["aabaa","bb","a","b","bbabb"],["aabaa","bb","a","bb",
     * "b","a","b","b"],["aabaa","bb","a","bb","b","a","bb"],["aabaa","bb","a","bb",
     * "bab","b"],["aabaa","bb","a","bbb","a","b","b"],["aabaa","bb","a","bbb","a",
     * "bb"],["aabaa","bb","abbba","b","b"],["aabaa","bb","abbba","bb"],["aabaa",
     * "bbabb","b","a","b","b"],["aabaa","bbabb","b","a","bb"],["aabaa","bbabb",
     * "bab","b"],["aabaa","bbabbbabb"]]
     * 
     * [["aabaabbabbba","bb"],["aabaabbabbba","b","b"],["aabaabba","bbbabb"],[
     * "aabaabba","bbbab","b"],["aabaabba","bbb","a","bb"],["aabaabba","bbb","a","b"
     * ,"b"],["aabaabba","bb","babb"],["aabaabba","bb","bab","b"],["aabaabba","bb",
     * "b","a","bb"],["aabaabba","bb","b","a","b","b"],["aabaabba","b","bbabb"],[
     * "aabaabba","b","bbab","b"],["aabaabba","b","bb","a","bb"],["aabaabba","b",
     * "bb","a","b","b"],["aabaabba","b","b","babb"],["aabaabba","b","b","bab","b"],
     * ["aabaabba","b","b","b","a","bb"],["aabaabba","b","b","b","a","b","b"],[
     * "aabaa","bbabbbabb"],["aabaa","bbabbbab","b"],["aabaa","bbabbb","a","bb"],[
     * "aabaa","bbabbb","a","b","b"],["aabaa","bbabb","babb"],["aabaa","bbabb","bab"
     * ,"b"],["aabaa","bbabb","b","a","bb"],["aabaa","bbabb","b","a","b","b"],[
     * "aabaa","bbab","bbabb"],["aabaa","bbab","bbab","b"],["aabaa","bbab","bb","a",
     * "bb"],["aabaa","bbab","bb","a","b","b"],["aabaa","bbab","b","babb"],["aabaa",
     * "bbab","b","bab","b"],["aabaa","bbab","b","b","a","bb"],["aabaa","bbab","b",
     * "b","a","b","b"],["aabaa","bb","abbba","bb"],["aabaa","bb","abbba","b","b"],[
     * "aabaa","bb","a","bbbabb"],["aabaa","bb","a","bbbab","b"],["aabaa","bb","a",
     * "bbb","a","bb"],["aabaa","bb","a","bbb","a","b","b"],["aabaa","bb","a","bb",
     * "babb"],["aabaa","bb","a","bb","bab","b"],["aabaa","bb","a","bb","b","a","bb"
     * ],["aabaa","bb","a","bb","b","a","b","b"],["aabaa","bb","a","b","bbabb"],[
     * "aabaa","bb","a","b","bbab","b"],["aabaa","bb","a","b","bb","a","bb"],[
     * "aabaa","bb","a","b","bb","a","b","b"],["aabaa","bb","a","b","b","babb"],[
     * "aabaa","bb","a","b","b","bab","b"],["aabaa","bb","a","b","b","b","a","bb"],[
     * "aabaa","bb","a","b","b","b","a","b","b"],["aabaa","b","babbbabb"],["aabaa",
     * "b","babbbab","b"],["aabaa","b","babbb","a","bb"],["aabaa","b","babbb","a",
     * "b","b"],["aabaa","b","babb","babb"],["aabaa","b","babb","bab","b"],["aabaa",
     * "b","babb","b","a","bb"],["aabaa","b","babb","b","a","b","b"],["aabaa","b",
     * "bab","bbabb"],["aabaa","b","bab","bbab","b"],["aabaa","b","bab","bb","a",
     * "bb"],["aabaa","b","bab","bb","a","b","b"],["aabaa","b","bab","b","babb"],[
     * "aabaa","b","bab","b","bab","b"],["aabaa","b","bab","b","b","a","bb"],[
     * "aabaa","b","bab","b","b","a","b","b"],["aabaa","b","b","abbba","bb"],[
     * "aabaa","b","b","abbba","b","b"],["aabaa","b","b","a","bbbabb"],["aabaa","b",
     * "b","a","bbbab","b"],["aabaa","b","b","a","bbb","a","bb"],["aabaa","b","b",
     * "a","bbb","a","b","b"],["aabaa","b","b","a","bb","babb"],["aabaa","b","b","a"
     * ,"bb","bab","b"],["aabaa","b","b","a","bb","b","a","bb"],["aabaa","b","b","a"
     * ,"bb","b","a","b","b"],["aabaa","b","b","a","b","bbabb"],["aabaa","b","b","a"
     * ,"b","bbab","b"],["aabaa","b","b","a","b","bb","a","bb"],["aabaa","b","b","a"
     * ,"b","bb","a","b","b"],["aabaa","b","b","a","b","b","babb"],["aabaa","b","b",
     * "a","b","b","bab","b"],["aabaa","b","b","a","b","b","b","a","bb"],["aabaa",
     * "b","b","a","b","b","b","a","b","b"],["aaba","abbabbba","bb"],["aaba",
     * "abbabbba","b","b"],["aaba","abba","bbbabb"],["aaba","abba","bbbab","b"],[
     * "aaba","abba","bbb","a","bb"],["aaba","abba","bbb","a","b","b"],["aaba",
     * "abba","bb","babb"],["aaba","abba","bb","bab","b"],["aaba","abba","bb","b",
     * "a","bb"],["aaba","abba","bb","b","a","b","b"],["aaba","abba","b","bbabb"],[
     * "aaba","abba","b","bbab","b"],["aaba","abba","b","bb","a","bb"],["aaba",
     * "abba","b","bb","a","b","b"],["aaba","abba","b","b","babb"],["aaba","abba",
     * "b","b","bab","b"],["aaba","abba","b","b","b","a","bb"],["aaba","abba","b",
     * "b","b","a","b","b"],["aaba","a","bbabbbabb"],["aaba","a","bbabbbab","b"],[
     * "aaba","a","bbabbb","a","bb"],["aaba","a","bbabbb","a","b","b"],["aaba","a",
     * "bbabb","babb"],["aaba","a","bbabb","bab","b"],["aaba","a","bbabb","b","a",
     * "bb"],["aaba","a","bbabb","b","a","b","b"],["aaba","a","bbab","bbabb"],[
     * "aaba","a","bbab","bbab","b"],["aaba","a","bbab","bb","a","bb"],["aaba","a",
     * "bbab","bb","a","b","b"],["aaba","a","bbab","b","babb"],["aaba","a","bbab",
     * "b","bab","b"],["aaba","a","bbab","b","b","a","bb"],["aaba","a","bbab","b",
     * "b","a","b","b"],["aaba","a","bb","abbba","bb"],["aaba","a","bb","abbba","b",
     * "b"],["aaba","a","bb","a","bbbabb"],["aaba","a","bb","a","bbbab","b"],["aaba"
     * ,"a","bb","a","bbb","a","bb"],["aaba","a","bb","a","bbb","a","b","b"],["aaba"
     * ,"a","bb","a","bb","babb"],["aaba","a","bb","a","bb","bab","b"],["aaba","a",
     * "bb","a","bb","b","a","bb"],["aaba","a","bb","a","bb","b","a","b","b"],[
     * "aaba","a","bb","a","b","bbabb"],["aaba","a","bb","a","b","bbab","b"],["aaba"
     * ,"a","bb","a","b","bb","a","bb"],["aaba","a","bb","a","b","bb","a","b","b"],[
     * "aaba","a","bb","a","b","b","babb"],["aaba","a","bb","a","b","b","bab","b"],[
     * "aaba","a","bb","a","b","b","b","a","bb"],["aaba","a","bb","a","b","b","b",
     * "a","b","b"],["aaba","a","b","babbbabb"],["aaba","a","b","babbbab","b"],[
     * "aaba","a","b","babbb","a","bb"],["aaba","a","b","babbb","a","b","b"],["aaba"
     * ,"a","b","babb","babb"],["aaba","a","b","babb","bab","b"],["aaba","a","b",
     * "babb","b","a","bb"],["aaba","a","b","babb","b","a","b","b"],["aaba","a","b",
     * "bab","bbabb"],["aaba","a","b","bab","bbab","b"],["aaba","a","b","bab","bb",
     * "a","bb"],["aaba","a","b","bab","bb","a","b","b"],["aaba","a","b","bab","b",
     * "babb"],["aaba","a","b","bab","b","bab","b"],["aaba","a","b","bab","b","b",
     * "a","bb"],["aaba","a","b","bab","b","b","a","b","b"],["aaba","a","b","b",
     * "abbba","bb"],["aaba","a","b","b","abbba","b","b"],["aaba","a","b","b","a",
     * "bbbabb"],["aaba","a","b","b","a","bbbab","b"],["aaba","a","b","b","a","bbb",
     * "a","bb"],["aaba","a","b","b","a","bbb","a","b","b"],["aaba","a","b","b","a",
     * "bb","babb"],["aaba","a","b","b","a","bb","bab","b"],["aaba","a","b","b","a",
     * "bb","b","a","bb"],["aaba","a","b","b","a","bb","b","a","b","b"],["aaba","a",
     * "b","b","a","b","bbabb"],["aaba","a","b","b","a","b","bbab","b"],["aaba","a",
     * "b","b","a","b","bb","a","bb"],["aaba","a","b","b","a","b","bb","a","b","b"],
     * ["aaba","a","b","b","a","b","b","babb"],["aaba","a","b","b","a","b","b","bab"
     * ,"b"],["aaba","a","b","b","a","b","b","b","a","bb"],["aaba","a","b","b","a",
     * "b","b","b","a","b","b"],["aa","baabbabbbabb"],["aa","baabbabbbab","b"],["aa"
     * ,"baabbabbb","a","bb"],["aa","baabbabbb","a","b","b"],["aa","baabbabb","babb"
     * ],["aa","baabbabb","bab","b"],["aa","baabbabb","b","a","bb"],["aa","baabbabb"
     * ,"b","a","b","b"],["aa","baabbab","bbabb"],["aa","baabbab","bbab","b"],["aa",
     * "baabbab","bb","a","bb"],["aa","baabbab","bb","a","b","b"],["aa","baabbab",
     * "b","babb"],["aa","baabbab","b","bab","b"],["aa","baabbab","b","b","a","bb"],
     * ["aa","baabbab","b","b","a","b","b"],["aa","baabb","abbba","bb"],["aa",
     * "baabb","abbba","b","b"],["aa","baabb","a","bbbabb"],["aa","baabb","a",
     * "bbbab","b"],["aa","baabb","a","bbb","a","bb"],["aa","baabb","a","bbb","a",
     * "b","b"],["aa","baabb","a","bb","babb"],["aa","baabb","a","bb","bab","b"],[
     * "aa","baabb","a","bb","b","a","bb"],["aa","baabb","a","bb","b","a","b","b"],[
     * "aa","baabb","a","b","bbabb"],["aa","baabb","a","b","bbab","b"],["aa","baabb"
     * ,"a","b","bb","a","bb"],["aa","baabb","a","b","bb","a","b","b"],["aa","baabb"
     * ,"a","b","b","babb"],["aa","baabb","a","b","b","bab","b"],["aa","baabb","a",
     * "b","b","b","a","bb"],["aa","baabb","a","b","b","b","a","b","b"],["aa","baab"
     * ,"babbbabb"],["aa","baab","babbbab","b"],["aa","baab","babbb","a","bb"],["aa"
     * ,"baab","babbb","a","b","b"],["aa","baab","babb","babb"],["aa","baab","babb",
     * "bab","b"],["aa","baab","babb","b","a","bb"],["aa","baab","babb","b","a","b",
     * "b"],["aa","baab","bab","bbabb"],["aa","baab","bab","bbab","b"],["aa","baab",
     * "bab","bb","a","bb"],["aa","baab","bab","bb","a","b","b"],["aa","baab","bab",
     * "b","babb"],["aa","baab","bab","b","bab","b"],["aa","baab","bab","b","b","a",
     * "bb"],["aa","baab","bab","b","b","a","b","b"],["aa","baab","b","abbba","bb"],
     * ["aa","baab","b","abbba","b","b"],["aa","baab","b","a","bbbabb"],["aa","baab"
     * ,"b","a","bbbab","b"],["aa","baab","b","a","bbb","a","bb"],["aa","baab","b",
     * "a","bbb","a","b","b"],["aa","baab","b","a","bb","babb"],["aa","baab","b","a"
     * ,"bb","bab","b"],["aa","baab","b","a","bb","b","a","bb"],["aa","baab","b","a"
     * ,"bb","b","a","b","b"],["aa","baab","b","a","b","bbabb"],["aa","baab","b","a"
     * ,"b","bbab","b"],["aa","baab","b","a","b","bb","a","bb"],["aa","baab","b","a"
     * ,"b","bb","a","b","b"],["aa","baab","b","a","b","b","babb"],["aa","baab","b",
     * "a","b","b","bab","b"],["aa","baab","b","a","b","b","b","a","bb"],["aa",
     * "baab","b","a","b","b","b","a","b","b"],["aa","b","aabbabbba","bb"],["aa","b"
     * ,"aabbabbba","b","b"],["aa","b","aabba","bbbabb"],["aa","b","aabba","bbbab",
     * "b"],["aa","b","aabba","bbb","a","bb"],["aa","b","aabba","bbb","a","b","b"],[
     * "aa","b","aabba","bb","babb"],["aa","b","aabba","bb","bab","b"],["aa","b",
     * "aabba","bb","b","a","bb"],["aa","b","aabba","bb","b","a","b","b"],["aa","b",
     * "aabba","b","bbabb"],["aa","b","aabba","b","bbab","b"],["aa","b","aabba","b",
     * "bb","a","bb"],["aa","b","aabba","b","bb","a","b","b"],["aa","b","aabba","b",
     * "b","babb"],["aa","b","aabba","b","b","bab","b"],["aa","b","aabba","b","b",
     * "b","a","bb"],["aa","b","aabba","b","b","b","a","b","b"],["aa","b","aa",
     * "bbabbbabb"],["aa","b","aa","bbabbbab","b"],["aa","b","aa","bbabbb","a","bb"]
     * ,["aa","b","aa","bbabbb","a","b","b"],["aa","b","aa","bbabb","babb"],["aa",
     * "b","aa","bbabb","bab","b"],["aa","b","aa","bbabb","b","a","bb"],["aa","b",
     * "aa","bbabb","b","a","b","b"],["aa","b","aa","bbab","bbabb"],["aa","b","aa",
     * "bbab","bbab","b"],["aa","b","aa","bbab","bb","a","bb"],["aa","b","aa","bbab"
     * ,"bb","a","b","b"],["aa","b","aa","bbab","b","babb"],["aa","b","aa","bbab",
     * "b","bab","b"],["aa","b","aa","bbab","b","b","a","bb"],["aa","b","aa","bbab",
     * "b","b","a","b","b"],["aa","b","aa","bb","abbba","bb"],["aa","b","aa","bb",
     * "abbba","b","b"],["aa","b","aa","bb","a","bbbabb"],["aa","b","aa","bb","a",
     * "bbbab","b"],["aa","b","aa","bb","a","bbb","a","bb"],["aa","b","aa","bb","a",
     * "bbb","a","b","b"],["aa","b","aa","bb","a","bb","babb"],["aa","b","aa","bb",
     * "a","bb","bab","b"],["aa","b","aa","bb","a","bb","b","a","bb"],["aa","b","aa"
     * ,"bb","a","bb","b","a","b","b"],["aa","b","aa","bb","a","b","bbabb"],["aa",
     * "b","aa","bb","a","b","bbab","b"],["aa","b","aa","bb","a","b","bb","a","bb"],
     * ["aa","b","aa","bb","a","b","bb","a","b","b"],["aa","b","aa","bb","a","b","b"
     * ,"babb"],["aa","b","aa","bb","a","b","b","bab","b"],["aa","b","aa","bb","a",
     * "b","b","b","a","bb"],["aa","b","aa","bb","a","b","b","b","a","b","b"],["aa",
     * "b","aa","b","babbbabb"],["aa","b","aa","b","babbbab","b"],["aa","b","aa","b"
     * ,"babbb","a","bb"],["aa","b","aa","b","babbb","a","b","b"],["aa","b","aa","b"
     * ,"babb","babb"],["aa","b","aa","b","babb","bab","b"],["aa","b","aa","b",
     * "babb","b","a","bb"],["aa","b","aa","b","babb","b","a","b","b"],["aa","b",
     * "aa","b","bab","bbabb"],["aa","b","aa","b","bab","bbab","b"],["aa","b","aa",
     * "b","bab","bb","a","bb"],["aa","b","aa","b","bab","bb","a","b","b"],["aa","b"
     * ,"aa","b","bab","b","babb"],["aa","b","aa","b","bab","b","bab","b"],["aa","b"
     * ,"aa","b","bab","b","b","a","bb"],["aa","b","aa","b","bab","b","b","a","b",
     * "b"],["aa","b","aa","b","b","abbba","bb"],["aa","b","aa","b","b","abbba","b",
     * "b"],["aa","b","aa","b","b","a","bbbabb"],["aa","b","aa","b","b","a","bbbab",
     * "b"],["aa","b","aa","b","b","a","bbb","a","bb"],["aa","b","aa","b","b","a",
     * "bbb","a","b","b"],["aa","b","aa","b","b","a","bb","babb"],["aa","b","aa","b"
     * ,"b","a","bb","bab","b"],["aa","b","aa","b","b","a","bb","b","a","bb"],["aa",
     * "b","aa","b","b","a","bb","b","a","b","b"],["aa","b","aa","b","b","a","b",
     * "bbabb"],["aa","b","aa","b","b","a","b","bbab","b"],["aa","b","aa","b","b",
     * "a","b","bb","a","bb"],["aa","b","aa","b","b","a","b","bb","a","b","b"],["aa"
     * ,"b","aa","b","b","a","b","b","babb"],["aa","b","aa","b","b","a","b","b",
     * "bab","b"],["aa","b","aa","b","b","a","b","b","b","a","bb"],["aa","b","aa",
     * "b","b","a","b","b","b","a","b","b"],["aa","b","a","abbabbba","bb"],["aa","b"
     * ,"a","abbabbba","b","b"],["aa","b","a","abba","bbbabb"],["aa","b","a","abba",
     * "bbbab","b"],["aa","b","a","abba","bbb","a","bb"],["aa","b","a","abba","bbb",
     * "a","b","b"],["aa","b","a","abba","bb","babb"],["aa","b","a","abba","bb",
     * "bab","b"],["aa","b","a","abba","bb","b","a","bb"],["aa","b","a","abba","bb",
     * "b","a","b","b"],["aa","b","a","abba","b","bbabb"],["aa","b","a","abba","b",
     * "bbab","b"],["aa","b","a","abba","b","bb","a","bb"],["aa","b","a","abba","b",
     * "bb","a","b","b"],["aa","b","a","abba","b","b","babb"],["aa","b","a","abba",
     * "b","b","bab","b"],["aa","b","a","abba","b","b","b","a","bb"],["aa","b","a",
     * "abba","b","b","b","a","b","b"],["aa","b","a","a","bbabbbabb"],["aa","b","a",
     * "a","bbabbbab","b"],["aa","b","a","a","bbabbb","a","bb"],["aa","b","a","a",
     * "bbabbb","a","b","b"],["aa","b","a","a","bbabb","babb"],["aa","b","a","a",
     * "bbabb","bab","b"],["aa","b","a","a","bbabb","b","a","bb"],["aa","b","a","a",
     * "bbabb","b","a","b","b"],["aa","b","a","a","bbab","bbabb"],["aa","b","a","a",
     * "bbab","bbab","b"],["aa","b","a","a","bbab","bb","a","bb"],["aa","b","a","a",
     * "bbab","bb","a","b","b"],["aa","b","a","a","bbab","b","babb"],["aa","b","a",
     * "a","bbab","b","bab","b"],["aa","b","a","a","bbab","b","b","a","bb"],["aa",
     * "b","a","a","bbab","b","b","a","b","b"],["aa","b","a","a","bb","abbba","bb"],
     * ["aa","b","a","a","bb","abbba","b","b"],["aa","b","a","a","bb","a","bbbabb"],
     * ["aa","b","a","a","bb","a","bbbab","b"],["aa","b","a","a","bb","a","bbb","a",
     * "bb"],["aa","b","a","a","bb","a","bbb","a","b","b"],["aa","b","a","a","bb",
     * "a","bb","babb"],["aa","b","a","a","bb","a","bb","bab","b"],["aa","b","a","a"
     * ,"bb","a","bb","b","a","bb"],["aa","b","a","a","bb","a","bb","b","a","b","b"]
     * ,["aa","b","a","a","bb","a","b","bbabb"],["aa","b","a","a","bb","a","b",
     * "bbab","b"],["aa","b","a","a","bb","a","b","bb","a","bb"],["aa","b","a","a",
     * "bb","a","b","bb","a","b","b"],["aa","b","a","a","bb","a","b","b","babb"],[
     * "aa","b","a","a","bb","a","b","b","bab","b"],["aa","b","a","a","bb","a","b",
     * "b","b","a","bb"],["aa","b","a","a","bb","a","b","b","b","a","b","b"],["aa",
     * "b","a","a","b","babbbabb"],["aa","b","a","a","b","babbbab","b"],["aa","b",
     * "a","a","b","babbb","a","bb"],["aa","b","a","a","b","babbb","a","b","b"],[
     * "aa","b","a","a","b","babb","babb"],["aa","b","a","a","b","babb","bab","b"],[
     * "aa","b","a","a","b","babb","b","a","bb"],["aa","b","a","a","b","babb","b",
     * "a","b","b"],["aa","b","a","a","b","bab","bbabb"],["aa","b","a","a","b","bab"
     * ,"bbab","b"],["aa","b","a","a","b","bab","bb","a","bb"],["aa","b","a","a","b"
     * ,"bab","bb","a","b","b"],["aa","b","a","a","b","bab","b","babb"],["aa","b",
     * "a","a","b","bab","b","bab","b"],["aa","b","a","a","b","bab","b","b","a","bb"
     * ],["aa","b","a","a","b","bab","b","b","a","b","b"],["aa","b","a","a","b","b",
     * "abbba","bb"],["aa","b","a","a","b","b","abbba","b","b"],["aa","b","a","a",
     * "b","b","a","bbbabb"],["aa","b","a","a","b","b","a","bbbab","b"],["aa","b",
     * "a","a","b","b","a","bbb","a","bb"],["aa","b","a","a","b","b","a","bbb","a",
     * "b","b"],["aa","b","a","a","b","b","a","bb","babb"],["aa","b","a","a","b","b"
     * ,"a","bb","bab","b"],["aa","b","a","a","b","b","a","bb","b","a","bb"],["aa",
     * "b","a","a","b","b","a","bb","b","a","b","b"],["aa","b","a","a","b","b","a",
     * "b","bbabb"],["aa","b","a","a","b","b","a","b","bbab","b"],["aa","b","a","a",
     * "b","b","a","b","bb","a","bb"],["aa","b","a","a","b","b","a","b","bb","a","b"
     * ,"b"],["aa","b","a","a","b","b","a","b","b","babb"],["aa","b","a","a","b","b"
     * ,"a","b","b","bab","b"],["aa","b","a","a","b","b","a","b","b","b","a","bb"],[
     * "aa","b","a","a","b","b","a","b","b","b","a","b","b"],["a","abaabbabbba","bb"
     * ],["a","abaabbabbba","b","b"],["a","abaabba","bbbabb"],["a","abaabba","bbbab"
     * ,"b"],["a","abaabba","bbb","a","bb"],["a","abaabba","bbb","a","b","b"],["a",
     * "abaabba","bb","babb"],["a","abaabba","bb","bab","b"],["a","abaabba","bb","b"
     * ,"a","bb"],["a","abaabba","bb","b","a","b","b"],["a","abaabba","b","bbabb"],[
     * "a","abaabba","b","bbab","b"],["a","abaabba","b","bb","a","bb"],["a",
     * "abaabba","b","bb","a","b","b"],["a","abaabba","b","b","babb"],["a","abaabba"
     * ,"b","b","bab","b"],["a","abaabba","b","b","b","a","bb"],["a","abaabba","b",
     * "b","b","a","b","b"],["a","abaa","bbabbbabb"],["a","abaa","bbabbbab","b"],[
     * "a","abaa","bbabbb","a","bb"],["a","abaa","bbabbb","a","b","b"],["a","abaa",
     * "bbabb","babb"],["a","abaa","bbabb","bab","b"],["a","abaa","bbabb","b","a",
     * "bb"],["a","abaa","bbabb","b","a","b","b"],["a","abaa","bbab","bbabb"],["a",
     * "abaa","bbab","bbab","b"],["a","abaa","bbab","bb","a","bb"],["a","abaa",
     * "bbab","bb","a","b","b"],["a","abaa","bbab","b","babb"],["a","abaa","bbab",
     * "b","bab","b"],["a","abaa","bbab","b","b","a","bb"],["a","abaa","bbab","b",
     * "b","a","b","b"],["a","abaa","bb","abbba","bb"],["a","abaa","bb","abbba","b",
     * "b"],["a","abaa","bb","a","bbbabb"],["a","abaa","bb","a","bbbab","b"],["a",
     * "abaa","bb","a","bbb","a","bb"],["a","abaa","bb","a","bbb","a","b","b"],["a",
     * "abaa","bb","a","bb","babb"],["a","abaa","bb","a","bb","bab","b"],["a","abaa"
     * ,"bb","a","bb","b","a","bb"],["a","abaa","bb","a","bb","b","a","b","b"],["a",
     * "abaa","bb","a","b","bbabb"],["a","abaa","bb","a","b","bbab","b"],["a","abaa"
     * ,"bb","a","b","bb","a","bb"],["a","abaa","bb","a","b","bb","a","b","b"],["a",
     * "abaa","bb","a","b","b","babb"],["a","abaa","bb","a","b","b","bab","b"],["a",
     * "abaa","bb","a","b","b","b","a","bb"],["a","abaa","bb","a","b","b","b","a",
     * "b","b"],["a","abaa","b","babbbabb"],["a","abaa","b","babbbab","b"],["a",
     * "abaa","b","babbb","a","bb"],["a","abaa","b","babbb","a","b","b"],["a","abaa"
     * ,"b","babb","babb"],["a","abaa","b","babb","bab","b"],["a","abaa","b","babb",
     * "b","a","bb"],["a","abaa","b","babb","b","a","b","b"],["a","abaa","b","bab",
     * "bbabb"],["a","abaa","b","bab","bbab","b"],["a","abaa","b","bab","bb","a",
     * "bb"],["a","abaa","b","bab","bb","a","b","b"],["a","abaa","b","bab","b",
     * "babb"],["a","abaa","b","bab","b","bab","b"],["a","abaa","b","bab","b","b",
     * "a","bb"],["a","abaa","b","bab","b","b","a","b","b"],["a","abaa","b","b",
     * "abbba","bb"],["a","abaa","b","b","abbba","b","b"],["a","abaa","b","b","a",
     * "bbbabb"],["a","abaa","b","b","a","bbbab","b"],["a","abaa","b","b","a","bbb",
     * "a","bb"],["a","abaa","b","b","a","bbb","a","b","b"],["a","abaa","b","b","a",
     * "bb","babb"],["a","abaa","b","b","a","bb","bab","b"],["a","abaa","b","b","a",
     * "bb","b","a","bb"],["a","abaa","b","b","a","bb","b","a","b","b"],["a","abaa",
     * "b","b","a","b","bbabb"],["a","abaa","b","b","a","b","bbab","b"],["a","abaa",
     * "b","b","a","b","bb","a","bb"],["a","abaa","b","b","a","b","bb","a","b","b"],
     * ["a","abaa","b","b","a","b","b","babb"],["a","abaa","b","b","a","b","b","bab"
     * ,"b"],["a","abaa","b","b","a","b","b","b","a","bb"],["a","abaa","b","b","a",
     * "b","b","b","a","b","b"],["a","aba","abbabbba","bb"],["a","aba","abbabbba",
     * "b","b"],["a","aba","abba","bbbabb"],["a","aba","abba","bbbab","b"],["a",
     * "aba","abba","bbb","a","bb"],["a","aba","abba","bbb","a","b","b"],["a","aba",
     * "abba","bb","babb"],["a","aba","abba","bb","bab","b"],["a","aba","abba","bb",
     * "b","a","bb"],["a","aba","abba","bb","b","a","b","b"],["a","aba","abba","b",
     * "bbabb"],["a","aba","abba","b","bbab","b"],["a","aba","abba","b","bb","a",
     * "bb"],["a","aba","abba","b","bb","a","b","b"],["a","aba","abba","b","b",
     * "babb"],["a","aba","abba","b","b","bab","b"],["a","aba","abba","b","b","b",
     * "a","bb"],["a","aba","abba","b","b","b","a","b","b"],["a","aba","a",
     * "bbabbbabb"],["a","aba","a","bbabbbab","b"],["a","aba","a","bbabbb","a","bb"]
     * ,["a","aba","a","bbabbb","a","b","b"],["a","aba","a","bbabb","babb"],["a",
     * "aba","a","bbabb","bab","b"],["a","aba","a","bbabb","b","a","bb"],["a","aba",
     * "a","bbabb","b","a","b","b"],["a","aba","a","bbab","bbabb"],["a","aba","a",
     * "bbab","bbab","b"],["a","aba","a","bbab","bb","a","bb"],["a","aba","a","bbab"
     * ,"bb","a","b","b"],["a","aba","a","bbab","b","babb"],["a","aba","a","bbab",
     * "b","bab","b"],["a","aba","a","bbab","b","b","a","bb"],["a","aba","a","bbab",
     * "b","b","a","b","b"],["a","aba","a","bb","abbba","bb"],["a","aba","a","bb",
     * "abbba","b","b"],["a","aba","a","bb","a","bbbabb"],["a","aba","a","bb","a",
     * "bbbab","b"],["a","aba","a","bb","a","bbb","a","bb"],["a","aba","a","bb","a",
     * "bbb","a","b","b"],["a","aba","a","bb","a","bb","babb"],["a","aba","a","bb",
     * "a","bb","bab","b"],["a","aba","a","bb","a","bb","b","a","bb"],["a","aba","a"
     * ,"bb","a","bb","b","a","b","b"],["a","aba","a","bb","a","b","bbabb"],["a",
     * "aba","a","bb","a","b","bbab","b"],["a","aba","a","bb","a","b","bb","a","bb"]
     * ,["a","aba","a","bb","a","b","bb","a","b","b"],["a","aba","a","bb","a","b",
     * "b","babb"],["a","aba","a","bb","a","b","b","bab","b"],["a","aba","a","bb",
     * "a","b","b","b","a","bb"],["a","aba","a","bb","a","b","b","b","a","b","b"],[
     * "a","aba","a","b","babbbabb"],["a","aba","a","b","babbbab","b"],["a","aba",
     * "a","b","babbb","a","bb"],["a","aba","a","b","babbb","a","b","b"],["a","aba",
     * "a","b","babb","babb"],["a","aba","a","b","babb","bab","b"],["a","aba","a",
     * "b","babb","b","a","bb"],["a","aba","a","b","babb","b","a","b","b"],["a",
     * "aba","a","b","bab","bbabb"],["a","aba","a","b","bab","bbab","b"],["a","aba",
     * "a","b","bab","bb","a","bb"],["a","aba","a","b","bab","bb","a","b","b"],["a",
     * "aba","a","b","bab","b","babb"],["a","aba","a","b","bab","b","bab","b"],["a",
     * "aba","a","b","bab","b","b","a","bb"],["a","aba","a","b","bab","b","b","a",
     * "b","b"],["a","aba","a","b","b","abbba","bb"],["a","aba","a","b","b","abbba",
     * "b","b"],["a","aba","a","b","b","a","bbbabb"],["a","aba","a","b","b","a",
     * "bbbab","b"],["a","aba","a","b","b","a","bbb","a","bb"],["a","aba","a","b",
     * "b","a","bbb","a","b","b"],["a","aba","a","b","b","a","bb","babb"],["a","aba"
     * ,"a","b","b","a","bb","bab","b"],["a","aba","a","b","b","a","bb","b","a","bb"
     * ],["a","aba","a","b","b","a","bb","b","a","b","b"],["a","aba","a","b","b","a"
     * ,"b","bbabb"],["a","aba","a","b","b","a","b","bbab","b"],["a","aba","a","b",
     * "b","a","b","bb","a","bb"],["a","aba","a","b","b","a","b","bb","a","b","b"],[
     * "a","aba","a","b","b","a","b","b","babb"],["a","aba","a","b","b","a","b","b",
     * "bab","b"],["a","aba","a","b","b","a","b","b","b","a","bb"],["a","aba","a",
     * "b","b","a","b","b","b","a","b","b"],["a","a","baabbabbbabb"],["a","a",
     * "baabbabbbab","b"],["a","a","baabbabbb","a","bb"],["a","a","baabbabbb","a",
     * "b","b"],["a","a","baabbabb","babb"],["a","a","baabbabb","bab","b"],["a","a",
     * "baabbabb","b","a","bb"],["a","a","baabbabb","b","a","b","b"],["a","a",
     * "baabbab","bbabb"],["a","a","baabbab","bbab","b"],["a","a","baabbab","bb","a"
     * ,"bb"],["a","a","baabbab","bb","a","b","b"],["a","a","baabbab","b","babb"],[
     * "a","a","baabbab","b","bab","b"],["a","a","baabbab","b","b","a","bb"],["a",
     * "a","baabbab","b","b","a","b","b"],["a","a","baabb","abbba","bb"],["a","a",
     * "baabb","abbba","b","b"],["a","a","baabb","a","bbbabb"],["a","a","baabb","a",
     * "bbbab","b"],["a","a","baabb","a","bbb","a","bb"],["a","a","baabb","a","bbb",
     * "a","b","b"],["a","a","baabb","a","bb","babb"],["a","a","baabb","a","bb",
     * "bab","b"],["a","a","baabb","a","bb","b","a","bb"],["a","a","baabb","a","bb",
     * "b","a","b","b"],["a","a","baabb","a","b","bbabb"],["a","a","baabb","a","b",
     * "bbab","b"],["a","a","baabb","a","b","bb","a","bb"],["a","a","baabb","a","b",
     * "bb","a","b","b"],["a","a","baabb","a","b","b","babb"],["a","a","baabb","a",
     * "b","b","bab","b"],["a","a","baabb","a","b","b","b","a","bb"],["a","a",
     * "baabb","a","b","b","b","a","b","b"],["a","a","baab","babbbabb"],["a","a",
     * "baab","babbbab","b"],["a","a","baab","babbb","a","bb"],["a","a","baab",
     * "babbb","a","b","b"],["a","a","baab","babb","babb"],["a","a","baab","babb",
     * "bab","b"],["a","a","baab","babb","b","a","bb"],["a","a","baab","babb","b",
     * "a","b","b"],["a","a","baab","bab","bbabb"],["a","a","baab","bab","bbab","b"]
     * ,["a","a","baab","bab","bb","a","bb"],["a","a","baab","bab","bb","a","b","b"]
     * ,["a","a","baab","bab","b","babb"],["a","a","baab","bab","b","bab","b"],["a",
     * "a","baab","bab","b","b","a","bb"],["a","a","baab","bab","b","b","a","b","b"]
     * ,["a","a","baab","b","abbba","bb"],["a","a","baab","b","abbba","b","b"],["a",
     * "a","baab","b","a","bbbabb"],["a","a","baab","b","a","bbbab","b"],["a","a",
     * "baab","b","a","bbb","a","bb"],["a","a","baab","b","a","bbb","a","b","b"],[
     * "a","a","baab","b","a","bb","babb"],["a","a","baab","b","a","bb","bab","b"],[
     * "a","a","baab","b","a","bb","b","a","bb"],["a","a","baab","b","a","bb","b",
     * "a","b","b"],["a","a","baab","b","a","b","bbabb"],["a","a","baab","b","a","b"
     * ,"bbab","b"],["a","a","baab","b","a","b","bb","a","bb"],["a","a","baab","b",
     * "a","b","bb","a","b","b"],["a","a","baab","b","a","b","b","babb"],["a","a",
     * "baab","b","a","b","b","bab","b"],["a","a","baab","b","a","b","b","b","a",
     * "bb"],["a","a","baab","b","a","b","b","b","a","b","b"],["a","a","b",
     * "aabbabbba","bb"],["a","a","b","aabbabbba","b","b"],["a","a","b","aabba",
     * "bbbabb"],["a","a","b","aabba","bbbab","b"],["a","a","b","aabba","bbb","a",
     * "bb"],["a","a","b","aabba","bbb","a","b","b"],["a","a","b","aabba","bb",
     * "babb"],["a","a","b","aabba","bb","bab","b"],["a","a","b","aabba","bb","b",
     * "a","bb"],["a","a","b","aabba","bb","b","a","b","b"],["a","a","b","aabba","b"
     * ,"bbabb"],["a","a","b","aabba","b","bbab","b"],["a","a","b","aabba","b","bb",
     * "a","bb"],["a","a","b","aabba","b","bb","a","b","b"],["a","a","b","aabba","b"
     * ,"b","babb"],["a","a","b","aabba","b","b","bab","b"],["a","a","b","aabba","b"
     * ,"b","b","a","bb"],["a","a","b","aabba","b","b","b","a","b","b"],["a","a","b"
     * ,"aa","bbabbbabb"],["a","a","b","aa","bbabbbab","b"],["a","a","b","aa",
     * "bbabbb","a","bb"],["a","a","b","aa","bbabbb","a","b","b"],["a","a","b","aa",
     * "bbabb","babb"],["a","a","b","aa","bbabb","bab","b"],["a","a","b","aa",
     * "bbabb","b","a","bb"],["a","a","b","aa","bbabb","b","a","b","b"],["a","a","b"
     * ,"aa","bbab","bbabb"],["a","a","b","aa","bbab","bbab","b"],["a","a","b","aa",
     * "bbab","bb","a","bb"],["a","a","b","aa","bbab","bb","a","b","b"],["a","a","b"
     * ,"aa","bbab","b","babb"],["a","a","b","aa","bbab","b","bab","b"],["a","a","b"
     * ,"aa","bbab","b","b","a","bb"],["a","a","b","aa","bbab","b","b","a","b","b"],
     * ["a","a","b","aa","bb","abbba","bb"],["a","a","b","aa","bb","abbba","b","b"],
     * ["a","a","b","aa","bb","a","bbbabb"],["a","a","b","aa","bb","a","bbbab","b"],
     * ["a","a","b","aa","bb","a","bbb","a","bb"],["a","a","b","aa","bb","a","bbb",
     * "a","b","b"],["a","a","b","aa","bb","a","bb","babb"],["a","a","b","aa","bb",
     * "a","bb","bab","b"],["a","a","b","aa","bb","a","bb","b","a","bb"],["a","a",
     * "b","aa","bb","a","bb","b","a","b","b"],["a","a","b","aa","bb","a","b",
     * "bbabb"],["a","a","b","aa","bb","a","b","bbab","b"],["a","a","b","aa","bb",
     * "a","b","bb","a","bb"],["a","a","b","aa","bb","a","b","bb","a","b","b"],["a",
     * "a","b","aa","bb","a","b","b","babb"],["a","a","b","aa","bb","a","b","b",
     * "bab","b"],["a","a","b","aa","bb","a","b","b","b","a","bb"],["a","a","b","aa"
     * ,"bb","a","b","b","b","a","b","b"],["a","a","b","aa","b","babbbabb"],["a","a"
     * ,"b","aa","b","babbbab","b"],["a","a","b","aa","b","babbb","a","bb"],["a","a"
     * ,"b","aa","b","babbb","a","b","b"],["a","a","b","aa","b","babb","babb"],["a",
     * "a","b","aa","b","babb","bab","b"],["a","a","b","aa","b","babb","b","a","bb"]
     * ,["a","a","b","aa","b","babb","b","a","b","b"],["a","a","b","aa","b","bab",
     * "bbabb"],["a","a","b","aa","b","bab","bbab","b"],["a","a","b","aa","b","bab",
     * "bb","a","bb"],["a","a","b","aa","b","bab","bb","a","b","b"],["a","a","b",
     * "aa","b","bab","b","babb"],["a","a","b","aa","b","bab","b","bab","b"],["a",
     * "a","b","aa","b","bab","b","b","a","bb"],["a","a","b","aa","b","bab","b","b",
     * "a","b","b"],["a","a","b","aa","b","b","abbba","bb"],["a","a","b","aa","b",
     * "b","abbba","b","b"],["a","a","b","aa","b","b","a","bbbabb"],["a","a","b",
     * "aa","b","b","a","bbbab","b"],["a","a","b","aa","b","b","a","bbb","a","bb"],[
     * "a","a","b","aa","b","b","a","bbb","a","b","b"],["a","a","b","aa","b","b","a"
     * ,"bb","babb"],["a","a","b","aa","b","b","a","bb","bab","b"],["a","a","b","aa"
     * ,"b","b","a","bb","b","a","bb"],["a","a","b","aa","b","b","a","bb","b","a",
     * "b","b"],["a","a","b","aa","b","b","a","b","bbabb"],["a","a","b","aa","b","b"
     * ,"a","b","bbab","b"],["a","a","b","aa","b","b","a","b","bb","a","bb"],["a",
     * "a","b","aa","b","b","a","b","bb","a","b","b"],["a","a","b","aa","b","b","a",
     * "b","b","babb"],["a","a","b","aa","b","b","a","b","b","bab","b"],["a","a","b"
     * ,"aa","b","b","a","b","b","b","a","bb"],["a","a","b","aa","b","b","a","b","b"
     * ,"b","a","b","b"],["a","a","b","a","abbabbba","bb"],["a","a","b","a",
     * "abbabbba","b","b"],["a","a","b","a","abba","bbbabb"],["a","a","b","a","abba"
     * ,"bbbab","b"],["a","a","b","a","abba","bbb","a","bb"],["a","a","b","a","abba"
     * ,"bbb","a","b","b"],["a","a","b","a","abba","bb","babb"],["a","a","b","a",
     * "abba","bb","bab","b"],["a","a","b","a","abba","bb","b","a","bb"],["a","a",
     * "b","a","abba","bb","b","a","b","b"],["a","a","b","a","abba","b","bbabb"],[
     * "a","a","b","a","abba","b","bbab","b"],["a","a","b","a","abba","b","bb","a",
     * "bb"],["a","a","b","a","abba","b","bb","a","b","b"],["a","a","b","a","abba",
     * "b","b","babb"],["a","a","b","a","abba","b","b","bab","b"],["a","a","b","a",
     * "abba","b","b","b","a","bb"],["a","a","b","a","abba","b","b","b","a","b","b"]
     * ,["a","a","b","a","a","bbabbbabb"],["a","a","b","a","a","bbabbbab","b"],["a",
     * "a","b","a","a","bbabbb","a","bb"],["a","a","b","a","a","bbabbb","a","b","b"]
     * ,["a","a","b","a","a","bbabb","babb"],["a","a","b","a","a","bbabb","bab","b"]
     * ,["a","a","b","a","a","bbabb","b","a","bb"],["a","a","b","a","a","bbabb","b",
     * "a","b","b"],["a","a","b","a","a","bbab","bbabb"],["a","a","b","a","a","bbab"
     * ,"bbab","b"],["a","a","b","a","a","bbab","bb","a","bb"],["a","a","b","a","a",
     * "bbab","bb","a","b","b"],["a","a","b","a","a","bbab","b","babb"],["a","a","b"
     * ,"a","a","bbab","b","bab","b"],["a","a","b","a","a","bbab","b","b","a","bb"],
     * ["a","a","b","a","a","bbab","b","b","a","b","b"],["a","a","b","a","a","bb",
     * "abbba","bb"],["a","a","b","a","a","bb","abbba","b","b"],["a","a","b","a","a"
     * ,"bb","a","bbbabb"],["a","a","b","a","a","bb","a","bbbab","b"],["a","a","b",
     * "a","a","bb","a","bbb","a","bb"],["a","a","b","a","a","bb","a","bbb","a","b",
     * "b"],["a","a","b","a","a","bb","a","bb","babb"],["a","a","b","a","a","bb","a"
     * ,"bb","bab","b"],["a","a","b","a","a","bb","a","bb","b","a","bb"],["a","a",
     * "b","a","a","bb","a","bb","b","a","b","b"],["a","a","b","a","a","bb","a","b",
     * "bbabb"],["a","a","b","a","a","bb","a","b","bbab","b"],["a","a","b","a","a",
     * "bb","a","b","bb","a","bb"],["a","a","b","a","a","bb","a","b","bb","a","b",
     * "b"],["a","a","b","a","a","bb","a","b","b","babb"],["a","a","b","a","a","bb",
     * "a","b","b","bab","b"],["a","a","b","a","a","bb","a","b","b","b","a","bb"],[
     * "a","a","b","a","a","bb","a","b","b","b","a","b","b"],["a","a","b","a","a",
     * "b","babbbabb"],["a","a","b","a","a","b","babbbab","b"],["a","a","b","a","a",
     * "b","babbb","a","bb"],["a","a","b","a","a","b","babbb","a","b","b"],["a","a",
     * "b","a","a","b","babb","babb"],["a","a","b","a","a","b","babb","bab","b"],[
     * "a","a","b","a","a","b","babb","b","a","bb"],["a","a","b","a","a","b","babb",
     * "b","a","b","b"],["a","a","b","a","a","b","bab","bbabb"],["a","a","b","a","a"
     * ,"b","bab","bbab","b"],["a","a","b","a","a","b","bab","bb","a","bb"],["a","a"
     * ,"b","a","a","b","bab","bb","a","b","b"],["a","a","b","a","a","b","bab","b",
     * "babb"],["a","a","b","a","a","b","bab","b","bab","b"],["a","a","b","a","a",
     * "b","bab","b","b","a","bb"],["a","a","b","a","a","b","bab","b","b","a","b",
     * "b"],["a","a","b","a","a","b","b","abbba","bb"],["a","a","b","a","a","b","b",
     * "abbba","b","b"],["a","a","b","a","a","b","b","a","bbbabb"],["a","a","b","a",
     * "a","b","b","a","bbbab","b"],["a","a","b","a","a","b","b","a","bbb","a","bb"]
     * ,["a","a","b","a","a","b","b","a","bbb","a","b","b"],["a","a","b","a","a","b"
     * ,"b","a","bb","babb"],["a","a","b","a","a","b","b","a","bb","bab","b"],["a",
     * "a","b","a","a","b","b","a","bb","b","a","bb"],["a","a","b","a","a","b","b",
     * "a","bb","b","a","b","b"],["a","a","b","a","a","b","b","a","b","bbabb"],["a",
     * "a","b","a","a","b","b","a","b","bbab","b"],["a","a","b","a","a","b","b","a",
     * "b","bb","a","bb"],["a","a","b","a","a","b","b","a","b","bb","a","b","b"],[
     * "a","a","b","a","a","b","b","a","b","b","babb"],["a","a","b","a","a","b","b",
     * "a","b","b","bab","b"],["a","a","b","a","a","b","b","a","b","b","b","a","bb"]
     * ,["a","a","b","a","a","b","b","a","b","b","b","a","b","b"]]
     */
}
